package com.ls.que126_130;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FindLadders {

    // 检查两个单词的相似性
    public boolean checkSame(String s1, String s2) {
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        boolean flag = false;
        for (int i=0; i<c1.length; i++) {
            if (c1[i] != c2[i]){
                if (!flag) {
                    flag = true;
                }else {
                    return false;
                }
            }
        }
        return true;
    }

    // 生成图 此处需要加上beginwords
    public Map<String, List<String>> get_grapg(List<String> wordList) {
        Map<String, List<String>> graph = new HashMap<>();
        //Map<String, Boolean> flag = new HashMap<>();
        for(int i=0; i<wordList.size(); i++){
            //flag.put(wordList.get(i), false);
            for (int j=0; j<wordList.size(); j++) {
                if (i!=j && checkSame(wordList.get(i), wordList.get(j))) {
                    if(!graph.containsKey(wordList.get(i))){
                        List<String> temp = new ArrayList<>();
                        graph.put(wordList.get(i), temp);
                    }
                    graph.get(wordList.get(i)).add(wordList.get(j));
                }
            }
        }
        return graph;
    }

    // 搜索图，得到所有的路径，尽可能的降低搜索复杂度。采用广度优先算法
    // Nodes : 记录当前层的节点
    // path： 记录当前层节点的路径
    // graph：记录图的连接关系
    // flag : 记录节点访问情况
    public List<List<String>> search(List<String> Nodes, Map<String, List<String>>path, Map<String, List<String>> graph, Map<String, Boolean> flag, String endWord) {
        if (Nodes.size() == 0) {
            return new ArrayList<>();
        }
        List<String> temp = new ArrayList<>();
        Map<String, List<String>> temp_path = new HashMap<>();
        boolean deep_flag = true;
        for(int i=0; i<Nodes.size(); i++) {
            List<String> links = graph.get(Nodes.get(i));
            for (int j=0; j<links.size(); j++) {
                if (links.get(j).equals(endWord))
                    deep_flag = false;
                if (!flag.get(links.get(j))) {
                    flag.put(links.get(j), true);
                    temp.add(links.get(j));

                    List<String> t = new ArrayList<>();
                    t.addAll(path.get(i));
                    t.add(links.get(j));
                    temp_path.put(links.get(j), t);
                }
            }
        }
        if (deep_flag) {
            return search(temp, temp_path, graph, flag, endWord);
        }else {
            // 检查路径结果，并返回数据
            List<List<String>> res = new ArrayList<>();
            for(String k : temp_path.keySet()) {
                List<String> p = temp_path.get(k);
                if (p.get(p.size()-1).equals(endWord)) {
                    res.add(p);
                }
            }
            return res;
        }

    }

    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        // 得到图
        wordList.add(0, beginWord);
        Map<String, List<String>> graph = get_grapg(wordList);
        return null;
    }
}
